/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package task_4;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

/**
 *
 * @author пользователь
 */
public class Hash {
    
    public 
            int size = 1000; //размер массива
            int coun = 0;  //количество внесенных элементов
    
    //конструктор
    public Hash()
    {
    }
    
    //работа хэш-таблицы
     public void Work(String str)
     {
          try
        {
            size = 1000;
            //Создаем массив списков
            ArrayList[] ar = new ArrayList[size];//массив слов
            ArrayList[] count = new ArrayList[size];//массив повторений слов
            for(int i = 0; i < ar.length; i++)
            {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }
            
            String ss; String word; int ch, m;
            //Поток из строки ss для считывания слов
            Scanner s;
            //Чтение из файла строки
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            
            while((ss = br.readLine())!= null)//проверка, не кончился ли файл
            {
                //Фильтр от знаков
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1); //удаление i-го элемента
                s = new Scanner(ss);
                while(s.hasNext()) //считали очередное слово из строки
                {
                    word = s.next();
                    int code = Hashh(word); //хеш-функция для слова
                    if(ar[code].isEmpty())
                    {
                        ar[code].add(word);
                        count[code].add(1);
                        coun++;
                    }
                    else
                    {
                        ch = ar[code].indexOf(word);
                        if(ch == -1) //такого слова нет в списке
                        {
                            ar[code].add(word);
                            count[code].add(1);
                            coun++;
                        }
                        else //такое слово уже есть в списке
                        {
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
                //обработка ресайза, ресайз  по массиву слов
                if(coun/size > 1.2) //если индекс заполнения превысил значения 1,2
                {
                    coun = 0; // снова обнуляем счетчик элементов
                    size += 1000; //увеличиваем на 1000 массив
                    //Создаем массив списков
                    ArrayList[] aro = new ArrayList[size];//массив слов
                    ArrayList[] counto = new ArrayList[size];//массив повторений слов
                    for(int i = 0; i < aro.length; i++)
                    {
                        aro[i] = new ArrayList();
                        counto[i] = new ArrayList(); 
                    } 
                    
                    //применение хэш - ф-ции ко всем элементам заполненной таблицы
                    int h; String exmp;
                    for(int i = 0; i < (size - 1000); i++)
                    {
                        for(int j = 0; j < ar[i].size(); j++)
                        {
                            exmp = ar[i].get(j).toString(); //слово текущее в талице
                            h = Hashh(exmp); //его хэш-значение
                            if(aro[h].isEmpty())
                            {
                                aro[h].add(exmp);
                                counto[h].add(count[i].get(j)); //добавляем число повторений этого слова из старого массива count
                                coun++;
                            }
                            else
                            {
                                ch = aro[h].indexOf(exmp);
                                if(ch == -1) //такого слова нет в списке
                                {
                                    aro[h].add(exmp);
                                    counto[h].add(count[i].get(j)); //добавляем число повторений этого слова из старого массива count
                                    coun++;
                                }
                            }
                        }
                    }
                    //присваеваем ссылки старым массивам на новые
                    ar = aro;
                    count = counto;
                }
            } 
            br.close(); 
            
            //Вывод на консоль
            for(int i = 0; i < size; i++)
            {
               for(int j = 0; j < ar[i].size(); j++)
               {
                   System.out.println( ar[i].get(j) + " - " + count[i].get(j) + " раз");
               }
            }
         }
       
        catch(java.io.IOException e)
        {
            e.printStackTrace();
        }
     } 
     
     public int Hashh(String word)
         {
             int h = 0; int mult = 32;
             for(int i = 0; i < word.length(); i++)
             {
                 h = (mult * h + Math.abs((int)word.charAt(i)-1038)) % size;//кодировка начиная с номера 1040
             }
             
             return h;
         }
     
     public int Hashh1(String word)
         {
             int h = 0; int mult = 60;
             for(int i = 0; i < word.length(); i++)
             {
                 h = (mult * h + Math.abs((int)word.charAt(i)-1038)) % size;//кодировка начиная с номера 1040
             }
             
             return h;
         }
     
     public int Hashh2(String word)
         {
             int h = 0; int mult = 1;
             for(int i = 0; i < word.length(); i++)
             {
                 h = (mult * h + Math.abs((int)word.charAt(i)-1038)) % size;//кодировка начиная с номера 1040
                 mult += 3;
             }
             //h = Math.abs(h) % size;
             return h;
         }
     
     //проверка эффективности метода для данного количества элементов в массиве
     public void Effective(int siz, String str)
     {
         
         try
         {
            size = siz;
            int qic = 0; //счетчик коллизий
            
            //Создаем массив списков
            ArrayList[] ar = new ArrayList[size];//массив слов
            ArrayList[] count = new ArrayList[size];//массив повторений слов
            for(int i = 0; i < ar.length; i++)
            {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }
            String ss; String word; int ch, m, code;
            //Поток из строки ss для считывания слов
            Scanner s;
            //Чтение из файла строки
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            
            
            // Для первой функции
            while((ss = br.readLine())!= null)//проверка, не кончился ли файл
            {
                //Фильтр от знаков
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1); //удаление i-го элемента
                s = new Scanner(ss);
                while(s.hasNext()) //считали очередное слово из строки
                {
                    word = s.next();
                    code = Hashh(word); //хеш-функция для слова
                    if(ar[code].isEmpty())
                    {
                        ar[code].add(word);
                        count[code].add(1);
                        coun++;
                    }
                    else //коллизия
                    {
                        qic++;
                        ch = ar[code].indexOf(word);
                        if(ch == -1) //такого слова нет в списке
                        {
                            ar[code].add(word);
                            count[code].add(1);
                            coun++;
                        }
                        else //такое слово уже есть в списке
                        {
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
                
            } 
            br.close(); 
            System.out.println("\nNumber of collusions of the Hashh method is " + qic);
            
            
            //Для второй функции
            qic = 0;
            for(int i = 0; i < ar.length; i++)
            {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }
            BufferedReader br1 = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            while((ss = br1.readLine())!= null)//проверка, не кончился ли файл
            {
                //Фильтр от знаков
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1); //удаление i-го элемента
                s = new Scanner(ss);
                while(s.hasNext()) //считали очередное слово из строки
                {
                    word = s.next();
                    code = Hashh1(word); //хеш-функция для слова
                    if(ar[code].isEmpty())
                    {
                        ar[code].add(word);
                        count[code].add(1);
                        coun++;
                    }
                    else //коллизия
                    {
                        qic++;
                        ch = ar[code].indexOf(word);
                        if(ch == -1) //такого слова нет в списке
                        {
                            ar[code].add(word);
                            count[code].add(1);
                            coun++;
                        }
                        else //такое слово уже есть в списке
                        {
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
            } 
            br1.close(); 
            System.out.println("\nNumber of collusions of the Hashh1 method is " + qic);
         
            
            //Для третьей функции
            qic = 0;
            for(int i = 0; i < ar.length; i++)
            {
                ar[i] = new ArrayList();
                count[i] = new ArrayList(); 
            }
            BufferedReader br2 = new BufferedReader(new InputStreamReader(new FileInputStream(str),("Windows-1251")));
            while((ss = br2.readLine())!= null)//проверка, не кончился ли файл
            {
                //Фильтр от знаков
                for(int i = 0; i < ss.length(); i++)
                if((ss.charAt(i) =='.')||(ss.charAt(i) ==',')||(ss.charAt(i) == '-')||(ss.charAt(i)== '!')||(ss.charAt(i)== '?')||(ss.charAt(i)== ')')||(ss.charAt(i)== '(')||(ss.charAt(i)== ':')||(ss.charAt(i)== ';'))
                    ss = ss.substring(0, i) + ss.substring(i+1); //удаление i-го элемента
                s = new Scanner(ss);
                while(s.hasNext()) //считали очередное слово из строки
                {
                    word = s.next();
                    code = Hashh2(word); //хеш-функция для слова
                    if(ar[code].isEmpty())
                    {
                        ar[code].add(word);
                        count[code].add(1);
                        coun++;
                    }
                    else //коллизия
                    {
                        qic++;
                        ch = ar[code].indexOf(word);
                        if(ch == -1) //такого слова нет в списке
                        {
                            ar[code].add(word);
                            count[code].add(1);
                            coun++;
                        }
                        else //такое слово уже есть в списке
                        {
                            m = (int)count[code].get(ch);
                            count[code].set(ch, m+1);
                        }
                    }
                }
            } 
            br2.close(); 
            System.out.println("\nNumber of collusions of the Hashh2 method is " + qic);
         }
         
        catch(java.io.IOException e)
        {
            e.printStackTrace();
        }
     }
}